package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/30 19:36
 */
public class No40_组合总和II {
    public static void main(String[] args) {
        Solution40 solution40 = new Solution40();
        int[] candidates = new int[]{5, 1, 1};
        List<List<Integer>> lists = solution40.combinationSum2(candidates, 8);
        System.out.println(lists);
    }
}

class Solution40 {
    List<List<Integer>> res = new ArrayList<>(); 
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> data = new ArrayList<>();
        for (int candidate : candidates) {
            addMapKeys(map, candidate);
        }
        combinationSum2(map, 0, target, data);
        return res;
    }

    public void combinationSum2(Map<Integer, Integer> map, int sum, int target, List<Integer> data) {
        if (sum == target) {
            List<Integer> dataCopy = new ArrayList<>(data);
            res.add(dataCopy);
            return;
        } else if (sum > target) {
            return;
        }
        
        //遍历map
        for (Map.Entry<Integer, Integer> mapData : map.entrySet()) {
            //key:元素
            int key = mapData.getKey();
            //key个数
            int valule = mapData.getValue();
            if (valule > 0) {
                //才可以下一轮,否则不可!!!
                //一定可以找到升降序
                if (data.size() != 0 && data.get(data.size() - 1) < key) {
                    continue;
                } else {
                    //跟上节基本一样
                    //元素个数-1
                    map.put(key, valule - 1);
                    sum += key;
                    data.add(key);
                    combinationSum2(map, sum, target, data);
                    //回溯
                    map.put(key, valule);
                    sum -= key;
                    data.remove(data.size() - 1);
                }
            } 
        }
    }

    //word_count
    public void addMapKeys(Map<Integer, Integer> map,int key) {
        if (map.get(key) == null) {
            map.put(key, 1);
        } else {
            map.put(key, map.get(key) + 1);
        } 
    }
}



    //List<List<Integer>> res = new ArrayList<>();
    //public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    //    List<Integer> listCandidates = new ArrayList<>();
    //    List<Integer> data = new ArrayList<>();
    //    for (int candidate : candidates) {
    //        listCandidates.add(candidate);
    //    }
    //    combinationSum2(listCandidates, 0, target, data);
    //    return res;
    //}
    //
    //public void combinationSum2(List<Integer> listCandidates, int sum, int target, List<Integer> data) {
    //    //递归结束条件
    //    if (sum == target) {
    //        //值传递
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        res.add(dataCopy);
    //        return;
    //    } else if (sum > target) {
    //        return;
    //    }
    //    
    //    //分析:由于第x轮遍历,元素如果重复,则第x+1轮元素组合必然重复,因此可以跳过
    //    //递归层优化:
    //    //处理递归层重复元素
    //    Set<Integer> set = new HashSet<>();
    //    for (int i = 0; i < listCandidates.size(); i++) {
    //        int remove = listCandidates.get(i);
    //        //去重,跳过
    //        if (set.add(remove)) {
    //            //找升降序
    //            if (data.size() != 0 && data.get(data.size() - 1) < remove) {
    //                continue;
    //            } else {
    //                listCandidates.remove(i);
    //                data.add(remove);
    //                sum += remove;
    //                combinationSum2(listCandidates, sum, target, data);
    //                //回溯
    //                listCandidates.add(i, remove);
    //                sum -= remove;
    //                data.remove(data.size() - 1);
    //            }
    //        } else {
    //            //第x+1轮必然重复,故跳过
    //            continue;
    //        }
    //    }
    //}



    //List<List<Integer>> res = new ArrayList<>();
    //Set<String> set = new HashSet<>();
    //public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    //    //1124  241  -> 241
    //    //暴力法走起!!!
    //    List<Integer> listCandidates = new ArrayList<>();
    //    //计算过程中加的值
    //    List<Integer> data = new ArrayList<>();
    //    for (int candidate : candidates) {
    //        listCandidates.add(candidate);
    //    }
    //    combinationSum2(listCandidates, 0, target, data);
    //    return res;
    //}
    //
    //public void combinationSum2(List<Integer> listCandidates, int sum, int target, List<Integer> data) {
    //    if (sum == target) {
    //        //值传递问题
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        //排序
    //        sortList(dataCopy);
    //        String base = "";
    //        for (int dataC : dataCopy) {
    //            //不正经算法,不要正经!随便写
    //            base += dataC + "UU)";
    //        }
    //        if (set.add(base)) {
    //            res.add(dataCopy);
    //        }
    //        return;
    //    } else if (sum > target) {
    //        return;
    //    }
    //    //由于candidates可变,因此用list表示
    //    for (int i = 0; i < listCandidates.size(); i++) {
    //        //哭:如果遇到重复的元素,你就哭吧!!!
    //        //if (data.size() != 0 && data.get(data.size() - 1) < listCandidates.get(i)) {
    //        //    continue;
    //        //}
    //        //获取当前元素
    //        int remove = listCandidates.get(i);
    //        sum += remove;
    //        data.add(remove);
    //        //移除
    //        listCandidates.remove(i);
    //        combinationSum2(listCandidates, sum, target, data);
    //        //回溯,从哪里去?从哪里回(哪个位置干掉,那个位置加回)
    //        listCandidates.add(i, remove);
    //        sum -= remove;
    //        data.remove(data.size() - 1);
    //        
    //    }
    //}
    //
    //public void sortList(List<Integer> dataCopy) {
    //    dataCopy.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            return o1 > o2 ? 1 : -1;
    //        }
    //    });
    //}




